package com.Questions.DFS;

import java.util.*;

/**
 * 王位继承顺序
 */
public class leetcode1600 {
    // 这个继承顺序就是 先遍历king的最年长的孩子Alice 然后再遍历Alice最年长的孩子
    // Jack 然后遍历Jack 最年长的孩子 没有 则遍历Alice最年长的孩子 没有 则遍历King最
    // 年长的孩子 剩下一个bob x是国王 返回空
    // 如果有死亡 直接在继承顺序中排除即可
    class ThroneInheritance {
        Map<String, List<String>> edges;// 一对多的长辈关系
        Set<String> dead;// 死亡列表
        String king;// 国王名字

        public ThroneInheritance(String kingName) {
            edges = new HashMap<String, List<String>>();
            dead = new HashSet<String>();
            king = kingName;
        }

        public void birth(String parentName, String childName) {
            List<String> children = edges.getOrDefault(parentName, new ArrayList<String>());
            children.add(childName);
            edges.put(parentName, children);
        }

        public void death(String name) {
            dead.add(name);
        }

        public List<String> getInheritanceOrder() {
            List<String> ans = new ArrayList<String>();
            preorder(ans, king);
            return ans;
        }

        private void preorder(List<String> ans, String name) {
            if (!dead.contains(name)) {
                ans.add(name);
            }
            List<String> children = edges.getOrDefault(name, new ArrayList<String>());
            for (String childName : children) {// 多叉树的先序遍历
                preorder(ans, childName);
            }
        }
    }
}
